public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }

        ListNode headA=list1;
        ListNode headB=list2;
        ListNode head;
        if(headA.val<headB.val){
            head=headA;
            headA=headA.next;
        }else{
            head=headB;
            headB=headB.next;
        }

        ListNode cur=head;
        ListNode curA=headA;
        ListNode curB=headB;

        while(curA!=null&&curB!=null){
            if(curA.val<curB.val){
                cur.next=curA;
                cur=curA;
                curA=curA.next;
            }else{
                cur.next=curB;
                cur=curB;
                curB=curB.next;
            }
        }

        if(curA!=null){
            cur.next=curA;
        }
        if(curB!=null){
            cur.next=curB;
        }

        return head;
    }
}

